#include <iostream> 
#include <vector>
#include <stack>
using namespace std;

bool dfs(vector<vector<char>>& grid,vector<vector<bool>>& visit,vector<vector<bool>>& path,int y,int x){
	
	int w = grid[0].size(),h = grid.size();

	
	stack<pair<int,int>> st;
	st.push(make_pair(y,x));
	bool flag = false;
	do{
		int i = st.top().first,j = st.top().second;
		char c = grid[i][j];
		
		auto temp = st.top();		
		int pi = st.top().first,pj = st.top().second;
		st.pop();	
		if( !st.empty() ){
			pi = st.top().first;
			pj = st.top().second;	
		}			
		st.push(temp);
		
		visit[i][j] = true;
		path[i][j] = true;
		if( i-1>=0 && !visit[i-1][j] && grid[i-1][j]==c) st.push(make_pair(i-1,j));			
		else if( i+1<h && !visit[i+1][j] && grid[i+1][j]==c ) st.push(make_pair(i+1,j));
		else if( j-1>=0 && !visit[i][j-1] && grid[i][j-1]==c) st.push(make_pair(i,j-1));
		else if( j+1<w && !visit[i][j+1] && grid[i][j+1]==c) st.push(make_pair(i,j+1));
		else{
			st.pop();
			path[i][j] = false;
		}

		if(( i-1>=0 && c==grid[i-1][j] && path[i-1][j] &&pi!=i-1)
			||( i+1<h && c==grid[i+1][j] && path[i+1][j] &&pi!=i+1) 
			||( j-1>=0 && c==grid[i][j-1] && path[i][j-1] &&pj!=j-1) 
			||( j+1<w && c==grid[i][j+1] && path[i][j+1] &&pj!=j+1) ){
			flag = true;
			break;
		}	
	}while( !st.empty() );
	return flag;
}
bool containsCycle(vector<vector<char>>& grid) {

	
	vector<vector<bool>> visit = *new vector<vector<bool>>(grid.size());
	vector<vector<bool>> path = *new vector<vector<bool>>(grid.size());
	for(int i=0;i<grid.size(); i++ ) path[i] = *new vector<bool>(grid[0].size(),false);
		
	for(int i=0;i<grid.size(); i++ ) visit[i] = *new vector<bool>(grid[0].size(),false);
	
	
    for(int i=0; i<grid.size(); i++){
        for(int j=0; j<grid[i].size(); j++){
        	cout << i<<" " << j << endl;
            if( !visit[i][j] && dfs(grid,visit,path,i,j) ) return true; 
        }            
    }
    return false;
}
int main(){
	vector<vector<char>> v = {{'a','a','a','a'},{'a','b','c','c'},{'a','b','b','a'},{'a','a','a','a'}};
	vector<vector<char>> v1 = {{'c','c','c','a'},{'c','d','c','c'},{'c','c','e','c'},{'f','c','c','c'}};
	cout << containsCycle(v);
	return 0;
}
